package com.itcam.otcbackend.demo;

import static cn.hutool.core.util.ArrayUtil.swap;

/**
 * @author : Cammy.Wu
 * Description : 
 */

public class SingleQuickSort {
    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1};
        singleQuickSort(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }

    private static void singleQuickSort(int[] nums) {
        int n = nums.length;
        quickSort(nums, 0, n - 1);
    }

    private static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int p = partition(nums, left, right);
        quickSort(nums, left, p - 1);
        quickSort(nums, p + 1, right);
    }

    private static int partition(int[] nums, int left, int right) {
        int x = left;
        int y = left;
        int pv = nums[right];
        while (y < right) {
            if (nums[y] < pv) {
                if (x != y) {
                    swap(nums, x, y);
                }
                x++;
            }
            y++;
        }
        swap(nums, x, right);
        return x;
    }
}
